In [ ]:
%%HTML
<style>
.container { width:100% }
</style>

Connect Four

This notebook defines the game Connect Four. You can play it online at: http://www.connectfour.org/connect-4-online.php.

Connect Four is played on a $6 \times 7$ board. Instead of Red and Yellow we call the players X and O. Player X starts. Player X and O take turns to choose columns that are not yet filled. When player X chooses column c, the first non-empty field in column c is filled with an "X". Likewise, when player O chooses column c, the first non-empty field in column c is filled with an "X". Rows are numbered from the bottom up, i.e. the bottom row is row $0$. The goal of the game for player X is to get four consecutive Xs into a row, column, or diagonal line, while player O needs to get four consecutive Os into a row, column, or diagonal line.


In [ ]:
Players = [ "X", "O" ]

States are represented as tuples of tuples. The game starts with an empty board. An empty field on the board is represented as the string ' '.


In [ ]:
Start = tuple( tuple(' ' for col in range(7)) for row in range(6))
Start

The function to_list transforms a tuple of tuples into a list of lists.


In [ ]:
to_list = lambda State: [list(row) for row in State]

The function to_tuple transforms a list of lists into a tuple of tuples.


In [ ]:
to_tuple = lambda State: tuple(tuple(row) for row in State)

The function find_empty takes two arguments:

  • State is a description of the board,
  • col specifies a column, i.e. it is an integer from the set $\{0, \cdots, 6\}$.

Given the State the function find_empty(State, col) returns the smallest $\texttt{row} \in \{0, \cdots, 5\}$ such that

    State[row][col] == ' '

holds. If the specified column is already completely filled, then instead None is returned.


In [ ]:
def find_empty(State, col):
    "your code here"

Given a State and the player who has the next move, the function next_states(State, player) computes the set of states that can be reached from State by a move of player.


In [ ]:
def next_states(State, player):
    "your code here"

The variable All_Lines collects the coordinates of all groups of four fields that are consecutive horizontally, vertically, or diagonally. For example, the variable All_Lines contains, among others, the following lists:

    [(0, 0), (0, 1), (0, 2), (0, 3)]
    [(0, 0), (1, 0), (2, 0), (3, 0)]
    [(1, 1), (2, 2), (3, 3), (4, 4)]

In [ ]:
All_Lines  = "your code here"

In [ ]:
All_Lines

Given a State the function top_line_filled(State) checks whether all marks in the top line of the given board are filled.


In [ ]:
def top_line_filled(State):
    "your code here"

The function utility takes two arguments:

  • State is a tuple of tuple representing the board.
  • player is a player.

The function returns 1 if player has won the game, -1 if the game is lost for player, 0 if its a draw, and None if the game has not yet been decided.


In [ ]:
def utility(State, player):
    "your code here"

The function heuristic tries to guess the value of a state. As it is never called in terminal states, it assumes that the game will be drawn.


In [ ]:
def heuristic(State, player):
    return 0.0

finished(State) is True if the game is over.


In [ ]:
def finished(State):
    return utility(State, "X") != None

The function get_move asks the user to input a move in the format r,c where r is the row and the c is the column where the next symbol is to be placed.


In [ ]:
def get_move(State):
    State = to_list(State)
    while True:
        col = input("Enter column here: ")
        col = int(col)
        row = find_empty(State, col)
        if row != None:
            State[row][col] = 'O'
            return to_tuple(State)
        else:
            print("Don't cheat.  Please try again.")

This function informs the user about the result of the game once the game is finished.


In [ ]:
def final_msg(State):
    if finished(State):
        if utility(State, "O") == 1:
            print("You have won!")
        elif utility(State, "O") == -1:
            print("You have lost!")
        else:
            print("It's a draw.");
        return True
    return False

Drawing the Board


In [ ]:
import ipycanvas as cnv

In [ ]:
size = 50

This function creates the canvas for the start state. It draws an empty board which is later used for the game.


In [ ]:
def create_canvas(Start):
    n = len(Start)
    canvas = cnv.Canvas(size=(size * 7, size * 8))
    display(canvas)
    return canvas

In [ ]:
import math

The function draw takes three arguments:

  • State is the current state of the game.
  • canvas is a canvas used to draw the state.
  • value is the value of the game for player X.

The function draws the given State onto canvas. Below that, the value is printed.


In [ ]:
def draw(State, canvas, value):
    canvas.clear()
    canvas.font = '36px sans-serif'
    canvas.text_align    = 'center'
    canvas.text_baseline = 'middle'
    for row in range(6):
        for col in range(7):
            x = col * size
            y = row * size
            canvas.line_width = 3.0
            canvas.stroke_rect(x, y, size, size)
            symbol = State[5-row][col]
            if symbol != ' ':
                x += size // 2
                y += size // 2
                if symbol == 'X':
                    canvas.fill_style ='red'
                else:
                    canvas.fill_style ='blue'
                canvas.fill_arc(x, y, 0.4*size, 0, 2*math.pi)
    canvas.font = '20px sans-serif'
    canvas.fill_style = 'black'
    for i in range(7):
        x = (i + 0.5) * size
        y = 6.4 * size
        canvas.fill_text(str(i), x, y) 
    x = 3.5 * size
    y = 7.4 * size
    canvas.fill_text(str(value), x, y)

In [ ]: